// 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

// 说明：

// 所有数字都是正整数。
// 解集不能包含重复的组合。 

// 暴露接口
const combinationSum3 = function (k: number, n: number) {
    const res: number[][] = []; // 结果数组
    const path: number[] = []; // 当前路径数组
    combinationSum3_DFS(k, n, res, path, 1);
    return res;
};
// 深度优先遍历--->回溯
function combinationSum3_DFS(k: number, n: number,
    res: number[][], path: number[], startPoint: number) {
    // 递归出口
    if (path.length === k) {
        if (n === 0) { // 满足条件则加入结果数组
            res.push(Array.from(path));
        }
        return;
    }
    // 深度优先遍历--->选择
    for (let i = startPoint; i <= 9; i++) {
        path.push(i);
        n -= i;
        startPoint++;
        combinationSum3_DFS(k, n, res, path, startPoint);// 遍历完所有的结果
        // 回溯算法部分
        n += i;
        path.pop();
    }
}

// 这道题其实依然可以用深度优先遍历结合回溯算法的板子来解决
// 思考的几个关键点：
// 1、深度优先搜索解决的是1-9之间数据组合的问题
// 2、startPoint用来解决每轮搜索起点的问题
// 3、用 k 来判断深度优先搜索是否到达了递归的出口
// 4、用 n 进行加减操作，以此来判断是否需要将当前的路径加入结果数组中
// 5、回溯算法用来解决 n 与 路径数字状态重置的问题。